class ElemNode:
    parent_nodes: list = []
    child_nodes: list = []
    traverse_flag: bool = False

    def __init__(self) -> None:
        self.parent_nodes = []
        self.child_nodes = []
        self.traverse_flag = False

    def add_parent(self, node):
        self.parent_nodes.append(node)

    def add_child(self, node):
        self.child_nodes.append(node)

    def remove_child(self, node):
        num_node = self.child_nodes.count(node)
        if(num_node):
            id_child = self.child_nodes.index(node)
            self.child_nodes.pop(id_child)
        else:
            raise ValueError()

    def remove_parent(self, node):
        num_node = self.parent_nodes.count(node)
        if(num_node):
            id_child = self.parent_nodes.index(node)
            self.parent_nodes.pop(id_child)
        else:
            raise ValueError()

    def top_to_bottom_traverse(self, func_call, result_list=[]):
        if(not self.traverse_flag):
            func_call(self, result_list)
            if(self.child_nodes):
                for child in self.child_nodes:
                    child.top_to_bottom_traverse(func_call, result_list)
    
    def bottom_to_top_traverse(self, func_call, result_list=[]):
        if(not self.traverse_flag):
            if(self.child_nodes):
                for child in self.child_nodes:
                    child.bottom_to_top_traverse(func_call, result_list)
            func_call(self, result_list)
    
    def by_layer(self, func_call, result_list=[]):
        for child in self.child_nodes:
            if(not child.traverse_flag):
                func_call(child, result_list)

        for child in self.child_nodes:
            child.by_layer(func_call, result_list)
    
    def is_top(self) -> bool:
        if(self.parent_nodes):
            return False
        else:
            return True

class Pile:
    top_nodes:list
    all_nodes:list
    def __init__(self) -> None:
        self.top_nodes = []   
        self.all_nodes = []

    def reset_traverse_flags(self):
        for node in self.all_nodes:
            node.traverse_flag = False


    def add_top(self, top_node:ElemNode, cmp_fun):
        # clear top nodes
        top_node.parent_nodes = []
        top_node.child_nodes = []

        # append top node to list
        self.all_nodes.append(top_node)

        # traverse each tree, append the bottom nodes in top_node.child_nodes
        checker = OverlapChecker(top_node, cmp_fun)

        self.reset_traverse_flags()
        top_nodes_copy = self.top_nodes.copy()
        for node in top_nodes_copy:
            node.bottom_to_top_traverse(checker, result_list=top_node.child_nodes)
            if(not node.is_top()):
                id = self.top_nodes.index(node)
                self.top_nodes.pop(id)

        self.top_nodes.append(top_node)

    def remove_top(self, top_node):
        for node in top_node.child_nodes:
            top_id = node.parent_nodes.index(top_node)
            node.parent_nodes.pop(top_id)
            if(not node.parent_nodes):
                self.top_nodes.append(node)
        
        top_id = self.top_nodes.index(top_node)
        self.top_nodes.pop(top_id)

        all_id = self.all_nodes.index(top_node)
        self.all_nodes.pop(all_id)

    def refresh_node_list(self):
        self.reset_traverse_flags()
        self.all_nodes = self.top_nodes.copy()
        for tree in self.top_nodes:
            tree.by_layer(append, result_list=self.all_nodes)
        
        # reverse
        self.all_nodes.reverse()


def set_traverse_flag(node:ElemNode, result=[]):
    node.traverse_flag = True

def append(node:ElemNode, node_list:list):
    node_list.append(node)
    node.traverse_flag = True

class OverlapChecker:
    top_node: ElemNode
    def __init__(self, top_node, cmp_fun) -> None:
        self.top_node = top_node
        self.cmp_fun = cmp_fun
    
    def __call__(self, bottom_node:ElemNode, bottom_node_list:list):
        if(self.cmp_fun(self.top_node, bottom_node)):
            # append 
            bottom_node_list.append(bottom_node)
            bottom_node.add_parent(self.top_node)
            bottom_node.bottom_to_top_traverse(set_traverse_flag)
        else:
            bottom_node.traverse_flag = True
        